/*
 * @lc app=leetcode.cn id=5 lang=golang
 * @lcpr version=30118
 *
 * [5] 最长回文子串
 */

// @lcpr-template-start

// @lcpr-template-end
// @lc code=start
func longestPalindrome(s string) string {
	n := len(s)
	if n == 0 {
		return ""
	}
	P := make([][]bool, n)
	for i := 0; i < n; i++ {
		P[i] = make([]bool, n)
	}

	start, end := 0, 0

	// 初始化边界情况
	for i := 0; i < n-1; i++ {
		P[i][i] = true
		if s[i] == s[i+1] {
			P[i][i+1] = true
			start, end = i, i+1
		}
	}
	P[n-1][n-1] = true

	for l := 3; l <= n; l++ {
		for i := 0; i <= n-l; i++ {
			j := i + l - 1
			P[i][j] = P[i+1][j-1] && s[i] == s[j]
			if l > end-start+1 && P[i][j] {
				end = j
				start = i
			}
		}
	}

	return s[start : end+1]
}

// @lc code=end

/*
// @lcpr case=start
// "babad"\n
// @lcpr case=end

// @lcpr case=start
// "cbbd"\n
// @lcpr case=end

*/

